1. Field of the Invention
The present invention relates to algorithmic processings performed on digital data handled by a microprocessor or an integrated circuit. The present invention more specifically relates to processings performed on digital data in cryptographic cyphering or authentication applications implementing so-called secured algorithms. In such applications, the data handled by the algorithms and on which basic operations (additions, multiplications) are performed must be protectable against piracy, that is, against external attacks aiming at discovering secret data and/or the calculation algorithm.
2. Discussion of the Related Art
For example, when an integrated circuit (be it a microprocessor or an operator in wired logic) executes a calculation on data, this calculation has an influence upon its power consumption. An analysis of the power consumption of the integrated circuit during the algorithm execution may enable a pirate to discover the processed data or the algorithm which executes them. Such attacks by analysis of the power consumption of an integrated circuit handling data are known as the SPA (single power analysis) or the DPA (differential power analysis).
An example of application of the present invention relates to authentication procedures of digital files (for example, audio files) or of electronic processing elements (for example, smart cards) to validate the authorization of the user to have access to information (for example, audio data or on-chip data).
For questions of calculation rapidity and of algorithm implementation ease, the numbers on which operations are desired to be performed by automatic calculation means may be factorized by application of the so-called Chinese remainder theorem (CRT).
The Chinese remainder theorem, applied to integers, may be expressed as follows. For any sequence of numbers mi (i ranging between 1 and n) prime to one another and for any sequence of integers xi, there is a single integer x smaller than the product of the sequence of prime numbers of the factorization base, such that for any i:xi=x modulo mi.
This means that, for a finite sequence of numbers mi, prime to one another, any number smaller than the product of this finite sequence can be represented uniquely, in a sequence of positive integers in a number equal to the number of elements of the sequence of numbers prime to one another. This representation is called the residue number system (RNS) representation.
In other words, for any integer x between 0 and M, where M represents the product of prime numbers mi of the factorization base, one may write:
                              x          =                                                                                    ∑                                      i                    =                    1                                    n                                ⁢                                                      x                    i                                    ·                                      m                    i                                    ·                                                                                                          M                        i                                                  -                          1                                                                                                                                  m                      i                                                                                                          M                          ,                                  ⁢                                            with                        ⁢                                                  ⁢            M                    =                                    ∏                              i                =                1                            n                        ⁢                          m              i                                      ,                              M            i                    =                      M                          m              i                                      ,                                  ⁢                              and  where                    ⁢                                          ⁢                                                                  M                i                                  -                  1                                                                                  m              i                                                          (formula  1)            is the inverse of number Mi modulo mi. Notation |. . . |M is used to designate a number (here, the result of the sum) modulo M.
The advantage of residue number systems is that operations such as addition, subtraction, and multiplication are simplified and can be executed in parallel architectures. In fact, the elementary operations can be performed on each integer of the factorization of the number to be calculated. The result is then obtained by applying above formula 1 to the result.
For example, two numbers x and y on which a calculation is desired to be performed are factorized by using the same base of prime numbers. After, the addition, subtraction, and product operations are carried out on the elements of the factorization, modulo the corresponding prime numbers. A set of values is obtained in the factorization base, which are recombined to obtain the result.
The major advantage of an automated execution of the calculations by means of integrated circuits is that the individual operations modulo the numbers of the factorization base involve numbers always having the same size, which enables execution of these calculations by means of parallel architectures and within a same duration.
However, a disadvantage is that the processed numbers are more easily detectable by the different attacks, especially, by power analysis of the integrated circuit.
Conventionally, to mask the processing of one or several numbers, these numbers are combined with random quantities, before the algorithmic processing.
A disadvantage is that this modifies the processed number(s), which imposes performing a reverse modification at the end of the processing to recover the expected result.
Another disadvantage is that the masking increases the processing complexity as well as the duration of the full calculation.
More generally, the residue number system applying the Chinese remainder theorem applies when the operations and operands are those of any finite body. For example, this system applies to a body of polynomials modulo an irreducible polynomial, or to the body of integers modulo a prime number.